1. Field of the Invention
The present invention relates to image processing apparatuses for compressing and decompressing digital data or binary image data and, more particularly, to an image processing apparatus such as a digital copy machine, a scanner or a printer, which uses an encoding and decoding system appropriate for a memory saving mechanism to save a frame buffer capacity.
2. Description of the Related Art
An image data compression technique is generally used in an image processing field so as to reduce a capacity of a memory for storing image data, or reduce a transmission time of image data. Various approaches are used for image data compression according to processing mode of the image data. When carrying out a printing process of image data, it is required to perform a high speed process such as printing an image after rotating the image on a memory having a limited capacity. For this reason, a fixed length compression method is used in many cases. GBTC (Generalized Block Truncation Coding) is known as a typical fixed length compression method.
Japanese Laid-Open Patent Application No. 10-285405 discloses a reference technique relevant to such a coding method. The conventional image data coding apparatus and image data coding method is applicable to a digital copy machine that handles image data as a digital signal. Such a digital copy machine reads image by a scanner, converts the read image data into a digital signal by an A/D converter, applies image processing such as a gamma conversion or an image-quality correction to the digital signal by an image processing part, and outputs an image by printing the image data on a record paper by an image output part.
The digital copy machine can store image data in a memory. Therefore, the image data stored in the memory can be used repeatedly. Moreover, processing and edit of image data such a rotation of an image can be performed by changing input and output addresses. Furthermore, a large amount of image data can be stored by encoding the image data and storing the encoded image data in a secondary memory unit such as a hard disk. It is also possible to output the image data after sorting.
However, there is a large amount of information of an image, and if the image information is stored in a memory as it is, a large memory capacity is needed. Since the unit price of a memory is high, a whole cost must become comparatively high and must use a large hard disk. Therefore, a cost of a memory and a hard disk is reduced by reducing a required memory capacity by storing compressed image data in a memory or a hard disk. A block encoding method, which is an image data compression method, compresses image data by decomposing the image data on an individual block basis. Intensity values Lij in one block are compressed by being converted by an algorithm show in FIG. 1 into an average value La (1 byte), a gradation width index Ld (1 byte) and quantization code φij (2 bit×16) for each pixel.
By this encoding method, an amount of data of 16 bytes of a 4×4-pixel block composed of 1-byte pixels is converted into 6 bytes, and the amount of data is compressed into three eighths of the amount of the original data. Qj is a quantization representation value at the time of decoding, and is a concentration value to which each code is assigned at the time of decoding. FIG. 2 is a block diagram of a digital copy machine having a function to compress and store image data in a memory and to store the encoded image data further in a hard disk. In a case of a normal image output, the digital copy machine reads an image as a signal for each pixel by a scanner 601, converts each signal into an 8-bit digital signal by an A/D converter 602, and applies image processing such as a gamma conversion by an image processing section 603. Then, the digital copy machine switches a signal change section 606 to B so as to send the image data to an image output section 607, and the image output section 607 outputs an image in accordance with the received image data.
A description will now be given of a case in which the image data is compressed and stored, and the encoded image data is decoded and output.
The scanner 601, the A/D converter 602 and the image processing section 603 perform the same process as the process of the normal output. A concentration value of the data from the image processing section 603 is encoded by the above-mentioned block encoding method. The code data corresponding to one page of the image is stored in a primary code storing section 605. After the code data for one page is stored, the code data is transferred from the primary code storing section 605 to a secondary code storing section 604 constituted by a hard disk or the like. Similarly, the code data of an original of a plurality of sheets is transferred to the secondary code storing section 604.
After the code data corresponding to the original of a desired number of sheets has been transferred to the secondary code storing section 604, the code data is read from the secondary code storing section 604 so as to carry out an output of the image data. First, the code data of the image stored in a head part of the secondary code storing section 604 is transferred to and stored in the primary code storing section 605, and the code data is decoded. Then, the signal change section 606 is switched to A, and the decoded data is sent to the image output section 607. The image output section 607 outputs an image in accordance with the decoded data.
The code data of the secondary code storing section 604 is sequentially read so as to repeat the above-mentioned operation. After decoding and outputting the code data of the image stored at the end, a one-set copy is output. A plurality of sets of copy can be output in the same manner.
A description will now be given, with reference to FIG. 3, of the primary code storing section 604 in detail. The primary code storing section 605 stores the image data, which is supplied on an individual line basis, in a four-line FIFO 701. Then, the above-mentioned block encoding is performed for each 4×4-pixel block by a primary encoding section 702, and the generated code data is stored in a code memory 703.
A description will now be given, with reference to FIG. 4, of the secondary code storing section 604. The secondary code storing section 604 comprises a secondary encoding section 802 and a storage device such as a hard disk 803. The code data corresponding to one sheet of the original stored in a code memory 801 is further encoded by the secondary coding section 802, and the further encoded data is stored in the hard disk 803. The secondary encoding section 802 generally uses a reversible encoding which does not have a difference between the data before encoding and the data at the time of decoding so that the code of block encoding can be decoded certainly.
Usually, as shown in FIG. 5, the average value La is encoded by using variable length coding such as WYLE coding of a differential value ΔL. The gradation width index Ld is encoded by using variable length coding such as a WYLE coding. φij is divided into high-order bits and lower-order bits, and encoded by a binary data encoding method such as MMR (Modified Modified Relative element address designate) method.
A description will be given below of a conventional printer image compression technology. As a method of compressing a binary image by small hardware, run-length image encoding of one-dimensional compression and MH coding such as a facsimile are known widely. As a method of compressing a binary image with a high compression rate, JBIG (Joint Bi-level Image experts Group) which is the international standard of a two-dimensional compression method is known. JBIG uses a QM-coder which is an arithmetic encoder as entropy coding. However, this method has a problem in that a context memory needed for the QM-coder as an arithmetic encoder and a line memory for producing a context require large-scale hardware and it is difficult to achieve a high-speed operation.
Japanese Laid-Open Patent Application No. 9-65147 discloses a modified MH coding method. When performing MH coding, a compression rate and a processing speed are improved by storing run lengths of black and white so as to produce a predetermined repetition code when a run length of either color matches an immediately preceding run length. Apparently, this method improves a compression rate and a processing speed by producing the repetitive code when coincidence of run lengths occurs. Accordingly, this method can improve the compression rate only when an amount of encoded data is smaller than an amount of a code word assigned to the data when the coincidence does not occur. However, since assignment of a shorter repetition code may increase a run length which does not incident relatively, it is difficult to obtain the code set having a sufficient compression rate with respect image data of which color frequently changes at a short interval.
Moreover, the code set disclosed in Japanese Laid-Open Patent Application No. 9-65147 is similar to the MH coding, and it is difficult to expect a high-speed operation since a large number of gates is required when a plurality of bits are processed in parallel.
Accordingly, the above-mentioned image encoding method can achieve a high compression rate for a specific image, but it is difficult to achieve a sufficient compression rate for image data having frequent color change at a short interval.
Japanese Laid-Open Patent Application No. 2000-217005 discloses a data encoding method solving the above-mentioned problem. The encoding method disclosed in this patent document converts a string of numerical values of run lengths into a predetermined code string on the basis of each color obtained by scanning data. A case where the numerical value of the run length is consistent with the numerical value of the immediately preceding run length of the same color is set as a consistency event, and a case where the consistence does not occur is set as an inconsistency event. A number of consecutive consistency events is set as a repetition number, and when the consistency event or consecution of the consistency events occurs, a repetition code corresponding to the number of consecutive events is generated. On the other hand, when the inconsistency event occurs, a code representing the numerical value of the above-mentioned run length is generated.
As mentioned above, conventionally, a copy image is compressed by a fixed length compression method (a method such as GBTC). In recent years, there is a demand for a compression rate greater than conventional due to a demand for storing image data in a memory or a hard disk. Thus, in order to satisfy such a demand, the code after the fixed length compression (GBTC) is further compressed by other compression apparatuses as mentioned above. However, there is an image data compression apparatus suitable for a characteristic of a printer image (which contains many repetitions of a binary image). Such a printer image and the above-mentioned copy image are individually compressed by separate encoders. Thus, there is a problem in that the scale of the hardware, a number of gates and the scale of software for achieving such data compression and encoding process are large.